package sort;

/**
* @description: 归并排序
* @author: wangjun
* @create: 2021-12-28
*/
public class MergeSortApplication {

    public static void main(String[] args) {
        int[] array = {2,1,4,5,6,7,3,8};
        int[] temp = new int[array.length];
        mergeSort(array,0,array.length-1);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }


    public static void mergeSort(int[] array,int left, int right, int[] temp){
        if (left < right) {
            int middle = (left + right) / 2;
            //左递归分解
            mergeSort(array, left, middle, temp);
            //右递归分解
            mergeSort(array, middle + 1, right, temp);
            //合并
//            merge(array, left, right, temp);
            merge1(array,left,middle,right);
        }
    }


    public static void merge(int[] array,int left, int right, int[] temp){
        int middle = (left + right) / 2;
        int i = left, j = middle + 1;
        int t = 0;
        while (i <= middle && j <= right){
            if(array[i] < array[j]){
                temp[t] = array[i];
                i++;
            }else {
                temp[t] = array[j];
                j++;
            }
            t++;
        }
        while (i <= middle){
            temp[t] = array[i];
            i++;
            t++;
        }
        while (j <= right){
            temp[t] = array[j];
            j++;
            t++;
        }
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right) {
            array[tempLeft] = temp[t];
            t++;
            tempLeft++;
        }
    }


    private static void mergeSort(int[] arr, int left, int right) {
        //对于递归，要处理递归到底的判断，这里就是left>=right。
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        //将左右两部分，利用临时数组进行归并
        merge1(arr, left, mid, right);
    }

    public static void merge1(int[] arr, int left, int mid, int right) {
        //临时辅助数组
        int[] temp = new int[right - left + 1];
        for (int i = left; i <= right; i++) {
            // 减去的left是原数组相对于临时数组的偏移量
            temp[i - left] = arr[i];
        }
        int i = left, j = mid + 1;
        for (int k = left; k <= right; k++) {
            // 检查左下标是否越界
            if (i > mid) {
                arr[k] = temp[j - left];
                j++;
                //检查右下标是否越界
            } else if (j > right) {
                arr[k] = temp[i - left];
                i++;
            } else if (temp[i - left] <= temp[j - left]) {
                arr[k] = temp[i - left];
                i++;
            } else {
                arr[k] = temp[j - left];
                j++;
            }
        }
    }
}
